Récursivité

Un programme qui fait appel à fonctions extérieures, des boucles et des tests est appelé itératif.
Un programme qui s’appelle lui même dans une des branches d’un test est appelé récursif.
Pour que ce soit possible, le langage utilisé doit posséder une pile dite "pile système" qui garde l’état de chaque variable et de chaque procédure rendue active à un moment donné, c’est à dire que le contexte est mis en pile dès qu’on appelle une procédure.
À la sortie de la procédure, le système retrouve l’état initial qu’il avait lors de l’appel à l’exception des modification faites par la procédure elle-même.
L’existence de cette pile rend possible qu’une procédure s’appelle elle-même.

La récursivité permet de résoudre un problème complexe, en un ou plusieurs sous-problèmes de structure identique, qui sont plus simples à résoudre.
L’expression, célèbre en informatique, pour décrire ce processus est DIVISER POUR REGNER

Toute fonction récursive doit avoir, grâce à une structure conditionnelle, une condition pour laquelle elle ne s’appelle pas elle-même. Sans cela, elle ne s’arrêterait jamais !
Cette condition s’appelle la condition d'arrêt ou le cas de base.
Par exemple, cette fonction qui permet de calculer x^y (y étant supposé > 0) :

Dans l’exemple précédent, la condition d'arrêt est la condition y <= 0 .
En pratique Python prévoit une profondeur de récursion maximum (par défaut 1000, mais modifiable), mais l’atteindre provoque une erreur, et surtout témoigne souvent d’une faute de programmation.
Il existe toujours une façon non récursive de réaliser une fonction donnée.
Écrire une fonction sous forme récursive est souvent plus naturel. En revanche, les grandes profondeurs de récursion peuvent solliciter fortement la mémoire et rendre son exécution plus lente.